package com.julius.design.suanfa.tree;

/**
 * @author julius
 * @date 2021-11-15 上午 9:53
 * <p>
 *      判断一个树是否为平衡二叉树
 *      输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 *      https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
 * </p>
 */
public class IsBalancedTree {


    /**
     * 深度优先搜索:::::
     *
     *      先序遍历：root left  right
     *      会重复计算
     * 使得每条路径的深度不能相差超过1
     * 左子树的最大深度和右子树的最大深度差值不能超过1
     * 要保证左子树和右子树都是平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        //找出当前树的左右最大深度并判断是否为平衡树
        int depthLeft = maxDepth(root.left);
        int depthRight = maxDepth(root.right);
        int abs = Math.abs(depthLeft - depthRight);

        if(abs > 1){
            return false;
        }
        //判断左子树的是否为平衡树
        boolean left = isBalanced(root.left);

        //判断右子树是否为平衡树
        boolean right = isBalanced(root.right);

        return left && right;
    }

    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = maxDepth(root.left);

        int right = maxDepth(root.right);

        return Math.max(left,right)+1;
    }


    /**
     * 后序遍历：
     *      left  right  root
     *
     * @param root
     * @return
     */
    public int recur(TreeNode root){
        //越过叶子节点
        if(root == null){
            return 0;
        }

        //左子树是否为平衡树
        int left = recur(root.left);
        if(left == -1){
            return -1;
        }

        //右子树是否为平衡树
        int right = recur(root.right);

        if(right == -1){
            return -1;
        }

        //计算当前节点是否平衡树
        return Math.abs(left-right) < 2 ?Math.max(left,right)+1:-1;
    }





    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
